package ec;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class GA {
	private List<Solution> _population = null;

	private int _tournament_size = 7;

	private int _mutation_prob = 25;

	private int _crossover_prob = 75;

	private int _elites_percent = 10;

	private FitnessEvaluator _fitness_evaluator = null;

	private int _cur_generation = 0;

	private Comparator<Solution> _population_sorter;

	private boolean _use_pruning = false;

	public GA(List<Solution> initial_population,
			FitnessEvaluator fitness_evaluator, int tournament_size,
			int mutation_prob, int crossover_prob, int elites_percent) {
		_population = initial_population;
		_fitness_evaluator = fitness_evaluator;
		_tournament_size = tournament_size;
		_mutation_prob = mutation_prob;
		_crossover_prob = crossover_prob;
		_elites_percent = elites_percent;
		_cur_generation = 0;

		_population_sorter = new Comparator<Solution>() {
			public int compare(Solution o1, Solution o2) {
				int order = 0;

				if (o1.getFitness() > o2.getFitness()) {
					order = -1;
				} else if (o1.getFitness() < o2.getFitness()) {
					order = 1;
				}

				return order;
			}
		};
	}

	public Generation runGeneration() {
		long start = System.currentTimeMillis();

		_cur_generation++;
		// evaluate the population
		for (int i = 0; i < _population.size(); i++) {
			Solution solution = _population.get(i);
			solution.setFitness(_fitness_evaluator.getFitness(solution));
		}

		// Create the data struct to return info about the generation
		Generation generation = new Generation(_cur_generation, _population);

		// For convience sort the population in decreasing fitness
		Collections.sort(_population, _population_sorter);

		//
		// create the new population
		List<Solution> new_population = new ArrayList<Solution>();

		selectElites(new_population);

		breed(new_population);

		// replace the old population with the new
		_population = new_population;

		long end = System.currentTimeMillis();
		generation.setElapsedTime(end - start);

		return generation;
	}

	private void breed(List<Solution> new_population) {
		while (new_population.size() < _population.size()) {
			int breed_type = (int) (Math.random() * 100);

			if (breed_type < _mutation_prob) {
				Solution parent = runTournament();
				new_population.add(parent.mutate());
			} else if ((breed_type -= _mutation_prob) < _crossover_prob) {
				Solution parentA = runTournament();
				Solution parentB = runTournament();

				List<Solution> children = parentA.crossover(parentB);
				new_population.add(children.get(0));
				if (new_population.size() < _population.size()) {
					new_population.add(children.get(1));
				}
			}

		}
	}

	private void selectElites(List<Solution> new_population) {
		int num_elites = (int) (_population.size() * (_elites_percent / 100d));
		for (int i = 0; i < num_elites; i++) {
			new_population.add(_population.get(i));
		}
	}

	private Solution runTournament() {
		Solution winner = null;
		double best_fitness = _fitness_evaluator.getWorstFitness();

		for (int i = 0; i < _tournament_size; i++) {
			int index = (int) (Math.random() * _population.size());

			if (_fitness_evaluator.compare(_population.get(index).getFitness(),
					best_fitness)) {
				winner = _population.get(index);
				best_fitness = winner.getFitness();
			}
		}

		return winner;
	}

	public void usePruning(boolean b) {
		_use_pruning = b;
	}
}
